package _17_剑指Offer;

import _17_剑指Offer.datastrcute.Node;

import java.util.HashMap;
import java.util.Map;

public class _35_剑指Offer复杂链表的复制 {

    public Node copyRandomList(Node head) {
        if (head == null) return head;
        // 复制Next指针
        for (Node node = head, copy = null; node != null; node = node.next.next) {
            copy = new Node(node.val);
            copy.next = node.next;
            node.next = copy;
        }
        // 复制Random指针
        for (Node node = head; node != null; node = node.next.next) {
            if (node.random != null) {
                node.next.random = node.random.next;
            }
        }
        // 分割链表
        Node newHead = head.next;
        Node node = head;
        while (node != null && node.next != null) {
            Node temp = node.next;
            node.next = temp.next;
            node = temp;
        }
        return newHead;
    }


    // 时间复杂度为 O(n)，空间复杂度也为O(n)
    public Node copyRandomList1(Node head) {
        Map<Node, Node> containers = new HashMap<>();
        Node temp = head;
        while (temp != null) {
            containers.put(temp, new Node(head.val));
            temp = temp.next;
        }
        return copyList(head, containers);
    }


    public Node copyList(Node head, Map<Node, Node> containers) {
        if (head == null) return head;

        Node node = copyList(head.next, containers);
        Node newNode = containers.get(head);
        Node random = containers.get(head.random);

        newNode.next = node;
        newNode.random = random;

        return newNode;
    }

}
